package leetcode.editor.cn;

public class P400NthDigit {
    public static void main(String[] args) {
        Solution solution = new P400NthDigit().new Solution();
        System.out.println(solution.findNthDigit(1000000000));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findNthDigit(int n) {
            Long start = 9L;
            int num = 1;
            Long sum = 9l;
            if (n < 10) {
                return n;
            }
            while (sum < n) {
                num++;
                start *= 10;
                if (sum >= n - start * num) {
                    break;
                }
                sum += start * num;
            }
            int gap = (int) (n - sum);
            int i = gap / num - 1;
            int j = gap % num;
            Long val = start / 9;
            if (j == 0) {
                val += i;
                String s = String.valueOf(val);
                return Integer.parseInt(s.charAt(s.length() - 1) + "");
            } else {
                val += i + 1;
                String s = String.valueOf(val);
                return Integer.parseInt(s.charAt(j - 1) + "");
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}